The invention relates to iterative decoding methods and iterative decoders. In particular, the invention relates to iterative decoding methods and iterative decoders used in conjunction with communication systems.
Iterative decoding schemes are well known in the art. Typically, these decoding schemes are used in receivers to decode encoded data that is transmitted across a channel from a transmitter to a receiver. One type of iterative decoding scheme is known as turbo decoding, which performs several iterations on each frame of received data until the data is properly decoded.
Several systems incorporate turbo decoders, such as, for example 3rd generation wireless communication systems and satellite communication systems.
For example, the channel coding scheme used in 3rd generation wireless systems is the PCCC (Parallel Concatenated Convolution Code) turbo code. The decoding algorithm is an iterative decoding algorithm. The PCCC turbo encoder structure as specified by 3GPP (3rd Generation Partnership Project) for the W-CDMA 3rd generation wireless systems is as shown below.
The transfer function of the 8-state constituent code for PCCC is
      G    ⁢          (      D      )        =      [          1      ,                        n          ⁢                      (            D            )                                    d          ⁢                      (            D            )                                ]  where,d(D)=1+D2+D3n(D)=1+D+D3.
The initial value of the PCCC encoder shift registers are zeros. The output of the PCCC encoder is punctured to produce coded bits corresponding to the desired code rate, ⅓. For a ⅓ code rate, none of the systematic or parity bits are punctured, and the output sequence is X(0), Y(0), Y′(0), X(1), Y(1), Y′(1), etc. Trellis termination is performed by taking the tail bits from the shift register feedback after all the information bits are encoded. Tail bits are added after the encoding of information bits. The first three tail bits shall be used to terminate the first constituent encoder (upper switch of FIG. 1 in a lower position) while the second constituent encoder is disabled. The last three tail bits shall be used to terminate the second constituent encoder (lower switch of FIG. 1 in a lower position) while the first constituent encoder is disabled. The transmitted bits for trellis termination shall then beX(t) Y(t) X(t+1) Y(t+1) X(t+2) Y(t+2) X′(t) Y′(t) X′(t+1) Y′(t+1) X′(t+2)Y′(t+2).
The Turbo code internal interleaver can be the PIL interleaver. The two most common decoding algorithms are the maximum a posteriori (MAP) algorithm and the soft output Viterbi algorithm (SOVA). The MAP algorithm gives the best performance but the SOVA algorithm provides reduced complexity. There are two forms of MAP algorithms in use for decoding the PCCC. These are the Bahl, Cocke, Jelenik and Raviv (BCJR) algorithm and the soft input soft output (SISO) algorithm. The SISO algorithm is essentially the same as the BCJR algorithm but has a more elegant form and has greater flexibility. A block diagram of the PCCC decoder is shown in FIG. 2.
The basic unit of the algorithm is the SISO module. The SISO module is a four port device that has two inputs and two outputs and which module implements the SISO algorithm. The module's inputs are the probabilities of the information symbols P(u; I) and code symbols P(c; I) labeling the edges of the code trellis, and the outputs are updates of these probabilities based upon knowledge of the trellis, P(u; O) and P(c; O), respectively.
FIG. 2 shows the use of the SISO module in a PCCC decoder. The inputs to the first SISO module are the probabilities of the code symbols and information symbols for the first code. The code symbol probabilities are similar to the branch metrics used in a Viterbi decoder and are determined from the demodulated signal amplitude and an estimate of the noise variance. The information symbol probabilities for the first code are the de-interleaved updated information symbol probabilities of the second code from the previous iteration (during the first iteration nothing is known about these probabilities, so the a priori distribution should be used).
Only the updated probabilities of the information symbols of the first code are used while the updated code symbol probabilities are ignored. The updated probabilities of the first code's information symbols are interleaved and become the input to the second SISO module, along with the second code's code symbol probabilities, again determined from the output of the demodulator and an estimate of the noise variance (note that only the parity bits from the second encoder are transmitted, so the probability of the punctured systematic bits are all 0:5). Again, the code symbol output is not used, and the probabilities of the information symbols from the second code are de-interleaved to become the input to the first SISO module during the next iteration.
After all iterations are complete, the probabilities of the information symbols from both codes can be combined by multiplying the probabilities. A final decision can then be made by choosing the information symbols with the highest probabilities.
The known decoders have several drawbacks. For instance, the performance of turbo decoders improve considerably as the number of iterations increase but the time taken for decoding also increases as the number of iterations increase. In particular, the time constraints for decoding (decoding time constraint per frame) in the W-CDMA system necessitates that the number of iterations that the system can perform within the given time constraints be optimized to the fullest. Typically, the system's decoding time constraint per frame is limited by the system's transmission and reception rate of frames so that the decoding time per frame does not exceed the transmission time per frame.
Although some decoders have addressed these concerns by fixing the number of iterations, such a solution can have drawbacks. A slow decoder may not be able to support the number of iterations required to achieve a particular performance level. A faster decoder, on the other hand, may be able to support a particular performance level, but the faster decoder will also perform a number of redundant iterations because each frame may not require the same number of iterations to achieve the same performance.
For example, if a performance level requires 12 iterations to be performed for a frame length of 1280, a decoder which can only support 3 iterations within the time constraint for that frame length will severely degrade performance.